home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / ai / dynamic.pro < prev    next >
Text File  |  1990-05-19  |  6KB  |  217 lines
  1. /*    USING TURBO PROLOG TO FORMULATE
  2.       DYNAMIC OPTIMIZATION MODELS
  3.  
  4.            JULY 12, 1986
  5.       GARRY J. VASS [72307,3311]  (c)
  6.       
  7.       
  8.       INTRODUCTION
  9.       ------------
  10.       Dynamic optimization is an operations research/
  11.       management science technique for expressing small
  12.       to medium scale problems with a single, deterministic
  13.       optimum value.  Dynamic optimization models are
  14.       frequently characterized by recursive formulations,
  15.       making them especially interesting as PROLOG exercises.
  16.       
  17.       The purpose of this file is to illustrate my findings
  18.       in this area.  Comments, suggestions, or efficiency 
  19.       improvements are welcome.
  20.       
  21.       The problem is taken from Chapter Eight of "PRINCIPLES
  22.       OF OPERATIONS RESEARCH", (Second Edition) by Harvey M.
  23.       Wagner.  Where possible, the program notation is 
  24.       consistent with the text.  Please refer to this 
  25.       text for a complete, lucid, and articulate
  26.       presentation of the problem.
  27.     
  28.     PROBLEM
  29.     -------
  30.     
  31.     Mark Off is planning a trip from New York (Point 1) to
  32.     San Francisco (Point 10), and concludes that he
  33.     is faced with a classical network routing problem.  
  34.     Each of the available routes will require four 
  35.     legs (or three intermediate stopping places).  
  36.     
  37.     From each stopping place, (or node), 
  38.     Mark can take one, two, or sometimes
  39.     three different "stages" with different costs
  40.     according to the table below (a map/graphic
  41.     is better, but the table will have to do):
  42.     
  43.     From Point     To Point           Cost
  44.     ----------     --------        ----
  45.     1        2                2
  46.     1        4        1
  47.     1        3        5                
  48.     2        5        10
  49.     2        6        12
  50.     3        5        5
  51.     3        6        10
  52.     3        7        7
  53.     4        6        15
  54.     4        7        13
  55.     5        8        7
  56.     5        9        5
  57.     6        8        3
  58.     6        9        4
  59.     7        8        7
  60.     7        9        1
  61.     8        10        1
  62.     9        10        4
  63.     
  64.     With limited resources, Mark Off elects to
  65.     locate the "optimal routing" (i.e. the one
  66.     with the minimum total cost).
  67.     
  68.     ANALYSIS
  69.     --------
  70.     The network itself is expressed with the
  71.     cij predicate, appearing in Wagner as the
  72.     "Cost" to go from "Point I" to "Point J".
  73.     To simplify the problem, the remaining 
  74.     decisions are added to the predicate.
  75.     For example, 
  76.         
  77.         cij(3,4,6,15)
  78.         
  79.     means that at Point 4, there are three
  80.     decisions to be made before the end is
  81.     reached and it is possible to go to Point
  82.     6 for a cost of 15.
  83.     
  84.         cij(1,9,10,4)
  85.         
  86.     means that at Point 9, there is one decision
  87.     yet to be made and it is possible to go from
  88.     Point 9 to Point 10 for a cost of 4.         
  89.     
  90.     Next, there is the "f" predicate which uses
  91.     six parameters:  remaining decisions, current
  92.     state (or "node", location, point, etc), 
  93.     a running cost total (intermediate), the 
  94.     final cost total, a running route list 
  95.     (intermediate), and a final route list.
  96.     The important ones here are the remaining
  97.     decisions, the current state, and the running
  98.     cost total.  The others are for cosmetics.
  99.     
  100.     f(0,10,T,....) is a terminal condition, meaning
  101.     that there are 0 decisions remaining and that
  102.     Mark is in Point 10 and has paid out T.
  103.     
  104.     
  105. */
  106. nowarnings
  107. domains
  108.     list = integer*
  109. predicates
  110.     optimal_route
  111.     
  112.     integer_list_minimum(integer, list, integer)
  113.     /*  start value, list, returned value  */
  114.     
  115.     cij(integer, integer, integer, integer)
  116.     /* remaining decisions, pointi, pointj, cost */
  117.     
  118.     f(integer, integer,integer,integer,list,list)
  119.     /* remaining decisions, pointi, cost */
  120.     
  121.         append(list,list,list) 
  122.  
  123. goal
  124.     optimal_route.    
  125.  
  126. clauses
  127.     optimal_route if
  128.         
  129.         /*  collect all possible costs going from point 1 to point 10
  130.             and put them into a list called Costlist.  */
  131.         
  132.         findall(Cost,f(4, Nodes, 0, Cost, Running_route, Final_route),Costlist) and
  133.         
  134.         /*  find the minimum value in Costlist and put it in 
  135.             the variable Minimum.  Assume that no cost will be
  136.             greater than 9999.  */
  137.             
  138.         integer_list_minimum(9999 ,Costlist, Minimum) and
  139.         
  140.         /*  go back and find a solution having a total cost
  141.             equal to the variable Minimum.  Put the nodes 
  142.             into the list variable Optimal_list.  */
  143.             
  144.         f(4, Anynodes, 0, Minimum, Anylist, Optimal_list) and 
  145.         
  146.         /*  write out the nodes in the optimal route and beg
  147.             everyone's forgiveness for not bothering to reverse
  148.             the list first  */
  149.             
  150.         nl and
  151.         write("Nodes in least cost route are:  ",Optimal_list) and
  152.         
  153.         /*  write out the minimum cost associated with the above list.  */
  154.         
  155.         nl and
  156.         write("Minimum cost = ",Minimum).
  157.         
  158.  
  159. /*  network predicates  */
  160.  
  161.     cij(1,8,10,1).
  162.     cij(1,9,10,4).
  163.     cij(2,5,8,7).
  164.     cij(2,6,8,3).
  165.     cij(2,7,8,7).
  166.     cij(2,5,9,5).
  167.     cij(2,6,9,4).
  168.     cij(2,7,9,1).
  169.     cij(3,2,5,10).
  170.     cij(3,2,6,12).
  171.     cij(3,3,5,5).
  172.     cij(3,3,6,10).
  173.     cij(3,3,7,7).
  174.     cij(3,4,6,15).
  175.     cij(3,4,7,13).
  176.     cij(4,1,2,2).
  177.     cij(4,1,3,5).
  178.     cij(4,1,4,1).
  179.  
  180.     /*  if there are zero decisions left to be made
  181.         and we are in point 10, then we must be done.  */
  182.  
  183.     f(0, 10, Runningmiles, Totalmiles, Routelist, Finallist) if
  184.         Totalmiles = Runningmiles and
  185.         Finallist  = Routelist.
  186.         
  187.     /*  if there are other than zero decisions left to 
  188.         be made and we are in state "State", then find
  189.         the next state in the network and keep track of
  190.         the miles.  Then see what happens in the next
  191.         state with one less    decision to be made.  */
  192.     
  193.     f(Remaining, State, Runningmiles, Totalmiles, Routelist, Finallist) if
  194.         cij(Remaining,  State, Nextstate, Miles)  and
  195.         append([State], Routelist, Newroutelist)  and
  196.         Newremaining =  Remaining - 1             and
  197.         Newmiles     =  Runningmiles +  Miles     and
  198.         f(Newremaining, Nextstate, Newmiles, Totalmiles, Newroutelist, Finallist).
  199.  
  200. /*  general purpose list predicates    */
  201.  
  202.         append([],L,L).
  203.         append([X|L1], L2, [X|L3]) if append(L1, L2, L3).
  204.  
  205.     integer_list_minimum(X,[],M) if M = X.        
  206.     integer_list_minimum(X, [H|T],M) if
  207.         H <= X and
  208.         integer_list_minimum(H,T,M).
  209.     integer_list_minimum(X, [H|T],M) if
  210.         integer_list_minimum(X,T,M).
  211.  
  212.  
  213.  
  214.  
  215. ease refer to this 
  216.       text for a complete, lucid, and articulate
  217.       presentation o